| 【Python】字符串的全排列（递归、非递归） | 您所在的位置：网站首页 › Python 递归 组合 › 【Python】字符串的全排列（递归、非递归） |
【Python】字符串的全排列（递归、非递归）
|
字符串的全排列
给定字符串S[0…N-1]，设计算法，枚举S的全排列 一、递归方式分析思路： 把s[0]固定在位置0上，[1,n-1]位置的数字全排（递归） 把s[1]固定在位置0上（把s[1]和s[0]交换），[1,n-1]位置的数字全排（递归） …… 如果第i个数字在前面出现过，则跳过 …… 把s[n-1]固定在位置0上（把s[n-1]和s[0]交换），[1,n-1]位置的数字全排（递归） Python代码如下： from copy import deepcopy def isduplicate(li, n, t): """ 从li的位置n到位置t-1，有没有和li[t]相等的数字 """ while n < t: if li[n] == li[t]: return True n += 1 return False def swap(li, i, j): if i == j: return temp = li[j] li[j] = li[i] li[i] = temp def permutation(li, size, n, result): """ [n,size]位置的数字全排 :param li:字符串数组 :param size: 字符串长度 :param n: 要交换的位置 :param result: 保留结果 :return: """ if n == size - 1: result.append(deepcopy(li)) return for i in list(range(n, size)): # 分别把(size-n)个数字固定到位置n if isduplicate(li, n, i): # 如果位置n出现过数字li[i]，跳过 continue swap(li, i, n) # 把s[n]和s[i]交换，把s[i]固定到位置n permutation(li, size, n + 1, result) # [n+1,size-1]位置的数字全排 swap(li, i, n) # 把s[n]和s[i]交换回来 if __name__ == '__main__': li = [1, 2, 2, 3] size = len(li) n = 0 result = [] permutation(li, size, n, result) for i in result: print(i)输入结果： [1, 2, 2, 3] [1, 2, 3, 2] [1, 3, 2, 2] [2, 1, 2, 3] [2, 1, 3, 2] [2, 2, 1, 3] [2, 2, 3, 1] [2, 3, 2, 1] [2, 3, 1, 2] [3, 2, 2, 1] [3, 2, 1, 2] [3, 1, 2, 2]字符串的全排列 递归示意图： 感觉不好想的，可以画个图，有助于理解 二、非递归方式分析思路： 起点：字典序最小的排列，例如122345。起点为正序 终点：字典序最大的排列，例如543221。终点为倒序 过程：按当前的排列找出刚好比它大的下一个排列 如：524321的下一个排列是531224 如何计算？ 我们从后向前找第一双相邻的递增数字，”21”、”32”、”43”都是非递增的，”24”即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），1、2都不行，3可以，将3和2交换得到”534221”，然后再将替换点后的字符串”4221”颠倒即得到”531224”。 对于像”543221”这种已经是最“大”的排列，返回false。 这样，一个while循环再加上计算字符串下一个排列的函数就可以实现非递归的全排列算法。 步骤：后找、小大、交换、翻转 后找：字符串中最后一个升序的位置i，即：S[i]= j or len(li) < j + 1: return while i < j: swap(li, i, j) i += 1 j -= 1 def get_next_permutation(li, size): # 后找：字符串中最后一个升序的位置i，即：S[i]= 0 and li[i] >= li[i + 1]: i -= 1 if i < 0: return False # 查找(小大)：S[i+1…N-1]中比S[i]大的最小值S[j] j = size - 1 while li[j] |
【本文地址】